#include "map.h"
#include "util.h"

// key采用取留余数法
// 解决冲突采用链地址法

typedef struct if_pair_struct {
	char *key;
	void *value;
} ifpair;


typedef struct if_node_struct {
	ifpair *pair;
    struct if_node_struct *next;
} ifnode;

typedef struct if_map_struct {
    BOOL safe;
    int capacity;
    int size;
    BOOL autoExpand;
    if_map_valueDeleteCallBack *valueCallback;
    // node集合
    ifnode **nodes;
} ifmap;

#define MAP_DEFAULT_SIZE 16
#define EXPAND_THRESHOLD_RATE 0.75
#define EXPAND_FACTOR 2

// hash算法
// put性能
static int hash(int capacity, char* key) {
    int h = 1;
    char ch;
    while (ch = *key++) {
        h = 31 * h + ch;
    }

    return abs(h % capacity);
}

// key的比较函数
// get性能
static BOOL compare(char *k1, char *k2) {
	return if_str_cmp(k1, k2) == 0;
}




// 删除pair，只会删除key，不会删除value
static void if_map_deletePair(ifpair *pair, BOOL safe, if_map_valueDeleteCallBack *cb) {
    if (pair) {
        // 只需要释放key
		if (cb) {
            cb(pair->key, pair->value);
        }
		if (pair->key && safe) {
			free(pair->key);
			pair->key = 0;
		}
        free(pair);
    }
}

// 删除pair，只会删除key，不会删除value
static void if_map_deleteNode(ifnode *node, BOOL deletePair, BOOL safe, if_map_valueDeleteCallBack *cb) {
    if (node) {
        // 只需要释放key
        if (deletePair && node->pair) {
            if_map_deletePair(node->pair, safe, cb);
        }
        free(node);
    }
}

// 在一个map中放入一个node
// check: 是否检查是否重复的key值
// 检查存在 返回之前的pair
static ifpair* if_map_putPair(ifmap *map, ifpair *pair, BOOL check) {
    int hsKey = hash(map->capacity, pair->key);
    ifnode *hashNode = map->nodes[hsKey];
    ifnode **ptr = NULL;

    if (hashNode) {
        // 存在node
        // 检查元素的key值
        if (check) {
            if (compare(pair->key, hashNode->pair->key)) {
                // 这个存在，那么替换pair
                ifpair *tmpPair = hashNode->pair;
                hashNode->pair = pair;

                return tmpPair;
            }
        }

        // 之前的位置上有node，那么需要循环链式遍历
        while (hashNode->next) {
            hashNode = hashNode->next;
        }
        ptr = &(hashNode->next);
    } else {

        // 不存在node
        ptr = &(map->nodes[hsKey]);
    }

    {
        // 构造一个新的node
        ifnode *node = (ifnode*) malloc (sizeof(ifnode));
        
		// 内存分配失败
		if (!node) {
			return NULL;
		}
		
		node->pair = pair;
        node->next = NULL;
		
        *ptr = node;

        // 大小+1
        map->size++;
    }

    return NULL;
}

// 对map进行扩容
static void expand(ifmap *map) {
	int i;

	register int preCapacity = map->capacity;
	// 保存之前的node数组
	register ifnode **preNodes = map->nodes;

	// 扩容
	map->capacity = map->capacity * EXPAND_FACTOR;
	map->nodes = (ifnode**)malloc(sizeof(ifnode*) * map->capacity);
	memset(map->nodes, 0, sizeof(ifnode*) * map->capacity);
	map->size = 0;
	// 移动node
	for (i = 0; i < preCapacity; i++) {
		ifnode *node = preNodes[i];
		while (node) {
			if_map_putPair(map, node->pair, FALSE);
			ifnode *tmp = node;
			node = node->next;
			free(tmp);
			//int hsKey = hash(map->capacity, node->pair->key);
			//map->nodes[hsKey] = node;
		}
	}

	free(preNodes);
}

// remove: 是否在得到的时候移出
static ifpair* if_map_getPair(ifmap* map, char* key, BOOL remove) {
    int hs = hash(map->capacity, key);
    ifnode *topNode = map->nodes[hs];
    ifnode *node = topNode;
    ifnode *preNode = NULL;
    ifpair *pair = NULL;

    while (node) {
        if (compare(key, node->pair->key)) {
            // 找到
            pair = node->pair;
            break;
        } else {
            // 没有找到
            preNode = node;
            node = node->next;
        }
    }

    if (pair && remove) {
        if (node == topNode) {
            // 位于散列表
            map->nodes[hs] = topNode->next;
        } else {
            // 位于链表
            preNode->next = node->next;
			if_map_deleteNode(node, FALSE, map->safe, NULL);
        }

        map->size--;
    }

    return pair;
}

// remove: 是否在得到的时候移出
static ifpair* if_map_getPairValue(ifmap* map, void* value, BOOL remove) {
    int i;
	ifpair *pair = NULL;

    for (i = 0; i < map->capacity; i++) {
        ifnode *topNode = map->nodes[i];
        ifnode *node = topNode;
        ifnode *preNode = NULL;

        while (node) {
            if (value == node->pair->value) {
                pair = node->pair;
                break;
            } else {
                // 没有找到
                preNode = node;
                node = node->next;
            }
        }

        if (pair && remove) {
            if (node == topNode) {
                // 位于散列表
                map->nodes[i] = topNode->next;
            } else {
                // 位于链表
                preNode->next = node->next;
				if_map_deleteNode(node, FALSE, map->safe, NULL);
            }

            map->size--;
        }

		if (pair) {
			break;
		}

    }

    return pair;
}

// 初始化一个map
// size: -1表示自动扩容，0表示没有大小，put/get任何都会失败
// safe: FALSE 表示map不会为key生成一份copy，这样key有可能会被你修改，则会出错; TRUE 则会为key生成一份copy，这样会导致内存稍微增大，但是key不会被修改
void* if_map_new(int capacity, BOOL safe, if_map_valueDeleteCallBack *vdcb) {
    ifmap *map = (ifmap*) malloc (sizeof(ifmap));
	memset(map, 0, sizeof(ifmap));

    if (capacity < 0) {
        // 自动扩容
        map->autoExpand = TRUE;
        map->size = 0;
        map->capacity = MAP_DEFAULT_SIZE;
    } else {
        map->autoExpand = FALSE;
        map->size = 0;
        map->capacity = capacity;
    }
	map->valueCallback = vdcb;
    map->safe = safe;
    // 分配节点指针空间
    map->nodes = (ifnode**) malloc (sizeof(ifnode*) * map->capacity);
    memset(map->nodes, 0, sizeof(ifnode*) * map->capacity);

	return map;
}

// 放入一个key value
// return: 如果之前存在这个key，那么之前的值会返回
void* if_map_put(void* m, char* key, void* value) {
    ifmap *map = (ifmap*) m;

    if (if_str_len(key) == 0) {
        return NULL;
    }

    // 判断是否超过限制
    if (!map->autoExpand && map->size >= map->capacity) {
        return NULL;
    }

    // 判断是否需要扩容
    if (map->autoExpand && map->size >= (map->capacity * EXPAND_THRESHOLD_RATE)) {
        // 开始扩容
        expand(map);
    }

    {
        // 构造一个pair
        void *ret = NULL;
        ifpair *pair = (ifpair*) malloc (sizeof(ifpair));

        // 为了安全
        if (map->safe) {
            key = if_str_clone(key);
        }

        pair->key = key;
        pair->value = value;
        pair = if_map_putPair(map, pair, TRUE);

        // 之前存在相同的key的pair
        if (pair) {
            ret = pair->value;
            if_map_deletePair(pair, map->safe, NULL);
        }

        return ret;
    }
}

// 得到value
void* if_map_get(void* m, char* key) {
    if (if_str_len(key) == 0 || !m) {
        return NULL;
    } else {
        ifmap *map = (ifmap*) m;
        void *ret = NULL;
        ifpair *pair = if_map_getPair(map, key, FALSE);
        if (pair) {
            ret = pair->value;
        }

        return ret;
    }
}
// map的value数量
int if_map_size(void* m) {
    if (!m) {
        return -1;
    } else {
        ifmap *map = (ifmap*)m;
        return map->size;
    }
}


// 得到所有values
// 使用完请释放内存
void** if_map_values(void* m) {
    if (!m) {
        return NULL;
    } else {
        int i;
        ifmap *map = (ifmap*)m;
        void **ret = (void**) malloc (sizeof(void*) * map->size);
		int valuePtr = 0;
        for (i = 0; i < map->capacity; i++) {
            ifnode *node = map->nodes[i];

            while (node) {
                ret[valuePtr++] = node->pair->value;
                node = node->next;
            }
        }

        return ret;
    }
}
// 是否存在
BOOL if_map_has(void* m, char* key) {
    if (!m) {
        return FALSE;
    } else {
        int i;
        ifmap *map = (ifmap*)m;
		ifnode *node = map->nodes[hash(map->capacity, key)];
        while (node) {
            if (compare(key, node->pair->key)) {
                return TRUE;
            }
            node = node->next;
        }

        return FALSE;
    }
}
// 是否包含这个value值，简单的value == value
BOOL if_map_contain(void* m, void* value) {
    if (!m) {
        return FALSE;
    } else {
        int i;
        ifmap *map = (ifmap*)m;
        for (i = 0; i < map->capacity; i++) {
            ifnode *node = map->nodes[i];

            while (node) {
                if (value == node->pair->value) {
                    return TRUE;
                }
                node = node->next;
            }
        }

        return FALSE;
    }
}
// 通过key，移出key-value
void* if_map_remove(void* m, char* key) {
    if (if_str_len(key) == 0 || !m) {
        return NULL;
    } else {
        ifmap *map = (ifmap*) m;
        void *ret = NULL;
        ifpair *pair = if_map_getPair(map, key, TRUE);
        if (pair) {
            ret = pair->value;
            if_map_deletePair(pair, map->safe, NULL);
        }

        return ret;
    }
}
// 通过value，移出key-value
// 通过遍历查找，没有用value来索引
void* if_map_removeValue(void* m, void* value) {
    if (!m) {
        return NULL;
    } else {
        ifmap *map = (ifmap*) m;
        void *ret = NULL;
        ifpair *pair = if_map_getPairValue(map, value, TRUE);
		if (pair) {
			ret = pair->value;
		}
        return ret;
    }
}

// 移出所有
void if_map_clear(void* m) {
    if (!m) {
        return;
    } else {
		int i;
        ifmap *map = (ifmap*) m;
		// 遍历node
        for (i = 0; i < map->capacity; i++) {
            ifnode *node = map->nodes[i];
            while (node) {
				ifnode *nextNode = node->next;
                if_map_deleteNode(node, TRUE, map->safe, map->valueCallback);
				node = nextNode;
            }
        }
		memset(map->nodes, 0, sizeof(ifnode*) * map->capacity);
		map->size = 0;
        return;
    }
}


// 释放一个map的内存
void if_map_delete(void* m) {
    if (!m) {
        return;
    } else {
		int i;
        ifmap *map = (ifmap*) m;

        // 遍历node
        for (i = 0; i < map->capacity; i++) {
            ifnode *node = map->nodes[i];

            while (node) {
                ifnode *nextNode = node->next;
                if_map_deleteNode(node, TRUE, map->safe, map->valueCallback);
				node = nextNode;
            }
        }

        free(map->nodes);
        free(map);
    }
}
